from .binary_tree_base import BinaryTree


class LinkedBinaryTree(BinaryTree):
    """Linked representation of a binary tree structure"""

    class _Node:
        """Tree node"""
        __slots__ = '_element', '_parent', '_left', '_right'

        def __init__(self, element, parent=None, left=None, right=None):
            self._element = element
            self._parent = parent
            self._left = left
            self._right = right

    class Position(BinaryTree.Position):
        """An abstraction representing the location if a single element"""
        def __init__(self, container, node):
            self._container = container
            self._node = node

        def element(self):
            """Return the element stored at this position"""
            return self._node._element

        def __eq__(self, other):
            """Return true if other position represents the same location"""
            return type(other) is type(self) and other._node is self._node

        def __ne__(self, other):
            """Return true if other does not represent the same lcoation"""
            return type(other) is not  type(self) or other._node is not self._node

    def _validate(self, p):
        """Return associated node, is position is valid"""
        if not isinstance(p, self.Position):
            raise TypeError("p must be proper Position type")
        if p._container is not self:
            raise ValueError("p does not belong to this container")
        if p._node._parent is p._node:
            raise ValueError("p is no longer valid")
        return p._node

    def _make_position(self, node):
        """Return Position instance for given node"""
        return self.Position(self, node) if node is not None else None

    def __init__(self):
        """Create an initially empty binary tree"""
        self._root = None
        self._size = 0

    def __len__(self):
        """Return the total number of elements in the tree"""
        return self._size

    def root(self):
        """Return position at the tree's root"""
        return self._make_position(self._root)

    def parent(self, p):
        """Return position representing p's parent"""
        node = self._validate(p)
        return self._make_position(node)

    def left(self, p):
        """"Return a Position representing p's left child"""
        node = self._validate(p)
        return self._make_position(node._left)

    def right(self, p):
        """Return a Postion representing p's right child"""
        node = self._validate(p)
        return self._make_position(node._right)

    def num_children(self, p):
        """Return the number of children that position p has"""
        node = self._validate(p)
        count = 0
        if node._left is not None:
            count += 1
        if node._right is not None:
            count += 1
        return count

    # ---------------------- Nonpublic method ----------------------#
    def _add_root(self, e):
        """Replace element e at the root of an empty tree and return new position"""
        if self._root is not None:
            raise ValueError("Root existed")
        self._size = 1
        self._root = self._Node(e)
        return self._make_position(self._root)

    def _add_left(self, p, e):
        """Create a new left child for Position p, storing element e."""
        node = self._validate(p)
        if node._left is not None:
            raise ValueError("Left child existed")
        self._size += 1
        node._left = self._Node(e, node)
        return self._make_position(node._left)

    def _add_right(self, p, e):
        """Create a new right child for Position p, storing element e"""
        node = self._validate(p)
        if node._right is not None:
            raise ValueError("Right child existed")
        self._size += 1
        node._right = self._Node(e, node)
        return self._make_position(node._right)

    def _replace(self, p, e):
        """Replace the element at position p with e, and return old element."""
        node = self._validate(p)
        old = node._element
        node._element = e
        return old

    def _delete(self, p):
        """移除位置p的节点，用该节点的孩子代替自己，若有，则返回该节点的存储的元素；若有两个孩子，则抛出错误"""
        node = self._validate(p)
        if self.num_children(node) == 2:
            raise ValueError("p has two child node")
        child = node._left if node._left else node._right
        if child is not None:
            child._parent = node._parent  # child grandparent become parent

        if node is self._root:
            self._root = child
        else:
            node_parent = node._parent
            if node is node_parent._left:
                node_parent._left = child
            else:
                node_parent._right = child
        self._size -= 1
        node._parent = node  # 处理丢弃的节点
        return node._element

    def _attach(self, p, t1, t2):
        """将子树T1、T2分别链接到节点p的左右子树，并将T1、T2置为空树；若p不是叶子节点，则抛出错误"""
        node = self._validate(p)

        if not self.is_leaf(p):
            raise ValueError("p is not leaf")
        if not t1.is_empty():  # attach t1 as left subtree of node
            self._size += 1
            t1._root._parent = node
            node._left = t1._root
            t1._root = None
            t1._size = 0
        if not t2.is_empty():  # attach t2 as right subtree of node
            self._size += 1
            t2._root._parent = node
            node._right = t2._root
            t2._root = None
            t2._size = 0

